package simple;

import data.TreeNode;
import javafx.util.Pair;

import java.util.Stack;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/5/24 14:01
 */
public class No108_将有序数组转换为二叉搜索树 {
    public static void main(String[] args) {
        Solution108 solution108 = new Solution108();
        int[] nums = new int[]{1, 4, 5, 8, 11, 21, 38, 59, 67, 88};
        TreeNode treeNode = solution108.sortedArrayToBST(nums);
        System.out.println();
    }
}

class Solution108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        //迭代法 BFS
        if (nums == null || nums.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(-9327589);
        sortedArrayToBST(root, nums, 0, nums.length - 1);
        return root;
    }

    public TreeNode sortedArrayToBST(TreeNode root, int[] nums, int red, int green) {
        int mid = (red + green) / 2;
        root.val = nums[mid];
        // pair(11,pair(0,9))
        Stack<Pair<TreeNode, Pair<Integer, Integer>>> stack = new Stack<>();
        stack.push(new Pair<>(root, new Pair<>(red, green)));

        while (!stack.isEmpty()) {
            //检查
            Pair<TreeNode, Pair<Integer, Integer>> checkTree = stack.pop();
            int newRed = checkTree.getValue().getKey();
            int newGreen = checkTree.getValue().getValue();
            mid = (newGreen + newRed) / 2;
            if (newGreen - newRed > 1) {
                //根结点一定有左右子节点
                checkTree.getKey().left = new TreeNode(nums[(newRed + mid - 1) / 2]);
                checkTree.getKey().right = new TreeNode(nums[(mid + 1 + newGreen) / 2]);
                stack.push(new Pair<>(checkTree.getKey().right, new Pair<>(mid + 1, newGreen)));
                stack.push(new Pair<>(checkTree.getKey().left, new Pair<>(newRed, mid - 1)));

            } else if (newGreen - newRed == 1) {
                checkTree.getKey().left = null;
                checkTree.getKey().right = new TreeNode(nums[(mid + 1 + newGreen) / 2]);
                stack.push(new Pair<>(checkTree.getKey().right, new Pair<>(mid + 1, newGreen)));
            } else if (8 == 8) {
                continue;
            }
        }
        return root;
    }
}


    //public TreeNode sortedArrayToBST(int[] nums) {
    //    if (nums.length == 0) {
    //        return null;
    //    }
    //    //二分查找
    //    TreeNode result = new TreeNode(-89359);
    //    sortedArrayToBST(result, nums, 0, nums.length - 1);
    //    return result;
    //}
    //
    //public TreeNode sortedArrayToBST(TreeNode root, int[] nums, int red, int green) {
    //    if (red > green) {
    //        return root;
    //    }
    //    //二分查找
    //    int mid = (red + green) / 2;
    //    if (root == null) {
    //        //根赋值
    //        root = new TreeNode(nums[mid]);
    //    } else {
    //        root.val = nums[mid];
    //    }
    //
    //    root.left = sortedArrayToBST(root.left, nums, red, mid - 1);
    //    root.right = sortedArrayToBST(root.right, nums, mid + 1, green);
    //    return root;
    //
    //}